package com.sunny.l37;

import java.util.ArrayList;

public class Solution {

    private ArrayList<ArrayList<Integer>> res = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        if(null == root)
            return res;
        ArrayList<Integer> list = new ArrayList<>();
        dfs(root, list, sum);
        return res;
    }

    public void dfs(TreeNode node, ArrayList<Integer> list, int sum){
        if(null == node.left && null == node.right){
            if(sum - node.val == 0){
                ArrayList<Integer> tmp = new ArrayList<>(list);
                tmp.add(node.val);
                res.add(tmp);
            }
        }else{
            sum -= node.val;
//            if(sum <= 0)
//                return;
            ArrayList<Integer> tmp = new ArrayList<>(list);
            tmp.add(node.val);
            if(null != node.left){
                dfs(node.left, tmp, sum);
            }
            if(null != node.right){
                dfs(node.right, tmp, sum);
            }
        }
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
